'''
Tkinter 实现插入排序
日期：2018-11-06
'''
import os
import tkinter
import tkinter.messagebox
from tkinter import *
import copy
import time
from PIL import Image, ImageTk


class Demonstrate:
    def __init__(self):
        # 设置主窗口
        self.root = Tk()
        self.root.geometry('1000x610')
        self.root.title('插入排序算法演示')
        self.root.resizable(width=False, height=False)

        # 设置菜单栏,主要包括算法的简介
        self.menubar = Menu(self.root)
        self.emenu = Menu(self.menubar)
        self.emenu.add_command(label='插入排序算法', command=self.insertAlgorithmInfo)
        self.menubar.add_cascade(label='算法简介', menu=self.emenu)
        self.root['menu'] = self.menubar

        # 设置画布
        self.canvas = Canvas(self.root, width=700, height=600, bg="white")
        self.canvas.pack()
        self.canvas.place(x=0, y=0)

        # 设置两个frame，frame1用来存放操作按钮，frame2用来显示中间过程
        self.frame1 = Frame(self.root)
        self.frame1.place(x=700, y=0)

        # 设置功能按钮
        self.button_start = Button(self.frame1, text='算法简介', width=42, command=self.insertAlgorithmInfo)
        self.button_start.grid(row=0, column=1, sticky=W + E + N + S)
        self.button_next = Button(self.frame1, text='单步演示', width=42, command=self.substepDemonstrate)
        self.button_next.grid(row=1, column=1, sticky=W + E + N + S)
        self.button_clear = Button(self.frame1, text='整体演示', width=42, command=self.entireDemonstrate)
        self.button_clear.grid(row=2, column=1, sticky=W + E + N + S)

        # frame用来表示算法演示的过程
        self.frame2 = Frame(self.root)
        self.frame2.place(x=700, y=100)
        self.label_show = Label(self.frame2, text='算法过程说明:').pack()

        self.text_show = Text(self.frame2, borderwidth=0)
        # 创建滚动条
        self.bar = Scrollbar(self.frame2)
        # 2个组件相互关联
        self.bar.config(command=self.text_show.yview)
        self.text_show.config(yscrollcommand=self.bar.set, width=40, height=39, background='#ffffff')
        # 2个组件分别打包
        self.bar.pack(side=RIGHT, fill=Y)
        self.text_show.pack(side=LEFT, fill=BOTH, expand=1)

        # 定义相关的变量
        self.imageDic = self.loadImage('./image/')  # 加载所有的图片资源,并储存到字典中
        self.sourceList = [['Google', 1096.5], ['Microsoft', 899.5], ['Apple', 2292.34], ['Amazon', 1778.6],
                           ['Tesla', 117.6], ['Netflix', 116.92], ['Facebook', 406.53], ['Intel', 627.6],
                           ['IBM', 791.39]]  # 待排序元素列表
        self.dataList = [1096.5, 899.5, 2292.34, 1778.6, 117.6, 116.92, 406.53, 627.6, 791.39]
        self.dataNumber = 9  # 待排序元素的个数
        self.max = max(self.dataList)  # 待排序列表里的最大值
        self.min = min(self.dataList)  # 待排序列表里面的最小值
        self.state = 'end'  # 状态，end：没有开始 run：正在进行
        self.sortResault = self.insertionSort()  # 插入排序的所有中间结果
        self.insertSortStep = len(self.sortResault)  # 插入排序的演示步数
        self.currentStep = 0  # 当前进行第几步
        self.preRectWidth = 40  # 每个单元图形的宽度，包括30的间隔和40的条形图宽度
        self.preRectHeihPrc = 450 / self.max  # 每个条形图高度比例，直接乘以排序列表里面的元素值

        content = '您好,欢迎来到本系统：\n\n【本系统的主要功能是演示插入排序的执行过程，待排序数据是一些知名it公司的年营业额。】\n\n【当前演示可以分为单步演示和整体演示，您可以分别点起查看】\n\n【单步点击：每点击一次即可可以查看一步的执行过程，知道算法执行完毕。\n整体演示：点击一次即可观看整个算法的执行流程，直至结束】\n\n\n'
        content += "当前待排序数据为：\n"
        for pre in self.sourceList:
            content += '公司：'+pre[0] + '   年营业额：' + str(pre[1]) +'\n'
        self.text_show.insert(END, content)
        self.text_show.config(state=DISABLED)

        self.root.mainloop()

    # 单步演示操作
    def substepDemonstrate(self):
        if self.state == 'end':
            if self.currentStep < self.dataNumber:
                for i in range(self.dataNumber + 1):
                    self.canvas.delete('la' + str(i), 'pa' + str(i), 'ta' + str(i), 'dire')
                # 已排序
                for i in range(self.currentStep + 1):
                    if self.sortResault[self.currentStep][1] == i:
                        self.drawBasicElemen(i, self.sortResault[self.currentStep][0][i][1], 2, 'red',
                                             self.sortResault[self.currentStep][0][i][0])
                    else:
                        self.drawBasicElemen(i, self.sortResault[self.currentStep][0][i][1], 2, 'blue',
                                             self.sortResault[self.currentStep][0][i][0])
                self.drawBasicElemen(self.currentStep + 1, self.sourceList[self.currentStep][1], 2, 'green',
                                     self.sourceList[self.currentStep][0])
                # 待排序
                for i in range(self.currentStep + 1, self.dataNumber):
                    self.drawBasicElemen(i + 1, self.sourceList[i][1], 2, 'blue', self.sourceList[i][0])

                self.drawDirection(self.currentStep + 1, self.sortResault[self.currentStep][1])
                self.canvas.update()

                self.text_show.config(state=NORMAL)
                content = '\n-----------第%d步操作-----------\n' % (self.currentStep)
                content += "当前待排序的元素为： " + str(self.sourceList[self.currentStep])+'\n'
                content += "排序后的有序列表为： " + str(self.sortResault[self.currentStep][0]) + " \n"
                content += "当前未排序的列表为：" + str(self.sourceList[self.currentStep + 1:]) + '\n\n'
                self.text_show.insert(END, content)
                self.text_show.config(state=DISABLED)

                self.currentStep += 1
            else:
                for i in range(self.dataNumber + 1):
                    self.canvas.delete('la' + str(i), 'pa' + str(i), 'ta' + str(i), 'dire')
                self.currentStep = 0
                tkinter.messagebox.showinfo(title='提示', message='您好，当前算法已经演示完毕')

                self.text_show.config(state=NORMAL)
                content = '当前插入算法已经演示完毕\n'
                content += '************************************\n\n'
                self.text_show.insert(END, content)
                self.text_show.config(state=DISABLED)
        else:
            tkinter.messagebox.showerror(title='警告', message='您好，请演示完毕后在执行单步执行操作')

    # 整体演示
    def entireDemonstrate(self):
        if self.state == 'end':
            self.state = 'run'
            # 初始部分
            # 文字说明部分
            self.text_show.config(state=NORMAL)
            content = '\n-----------第%d步操作-----------\n' % (0)
            content += "当前待排序的元素为： " + str(self.sourceList[0]) + '\n'
            content += "排序后的有序列表为： " + str(self.sortResault[0][0]) + " \n"
            content += "当前未排序的列表为：" + str(self.sourceList[0 + 1:]) + '\n\n'
            self.text_show.insert(END, content)
            self.text_show.config(state=DISABLED)
            for i in range(self.dataNumber + 1):
                self.canvas.delete('lu' + str(i), 'pu' + str(i), 'tu' + str(i))
                self.canvas.delete('la' + str(i), 'pa' + str(i), 'ta' + str(i), 'dire')
            self.currentStep = 0
            for i in range(self.dataNumber):
                self.drawBasicElemen(i, self.sourceList[i][1], 0, 'blue', self.sourceList[i][0])
            self.canvas.update()
            time.sleep(2)
            # 每一步动作
            for preStep in range(1, self.dataNumber):
                #文字说明部分
                self.text_show.config(state=NORMAL)
                content = '\n-----------第%d步操作-----------\n' % (preStep)
                content += "当前待排序的元素为： " + str(self.sourceList[preStep]) + '\n'
                content += "排序后的有序列表为： " + str(self.sortResault[preStep][0]) + " \n"
                content += "当前未排序的列表为：" + str(self.sourceList[preStep + 1:]) + '\n\n'
                self.text_show.insert(END, content)
                self.text_show.config(state=DISABLED)

                # 落下动作
                self.canvas.delete('lu' + str(preStep), 'pu' + str(preStep), 'tu' + str(preStep))
                self.drawBasicElemen(preStep, self.sourceList[preStep][1], 1, 'red', self.sourceList[preStep][0])
                self.canvas.update()
                time.sleep(0.3)
                # 变化动作,上面的向右移，下面的向左移
                for index in range(preStep, self.sortResault[preStep][1], -1):
                    self.canvas.delete('lu' + str(index - 1), 'pu' + str(index - 1), 'tu' + str(index - 1))
                    self.canvas.delete('ld' + str(index), 'pd' + str(index), 'td' + str(index))
                    self.drawBasicElemen(index, self.sortResault[preStep - 1][0][index - 1][1], 0, 'blue',
                                         self.sortResault[preStep - 1][0][index - 1][0])
                    self.drawBasicElemen(index - 1, self.sourceList[preStep][1], 1, 'red', self.sourceList[preStep][0])
                    self.canvas.update()
                    time.sleep(0.3)
                # 向上动作
                self.canvas.delete('ld' + str(self.sortResault[preStep][1]), 'pd' + str(self.sortResault[preStep][1]),
                                   'td' + str(self.sortResault[preStep][1]))
                self.drawBasicElemen(self.sortResault[preStep][1], self.sourceList[preStep][1], 0, 'red',
                                     self.sourceList[preStep][0])
                self.canvas.update()
                time.sleep(0.3)
                self.canvas.delete('lu' + str(self.sortResault[preStep][1]), 'pu' + str(self.sortResault[preStep][1]),
                                   'tu' + str(self.sortResault[preStep][1]))
                self.drawBasicElemen(self.sortResault[preStep][1], self.sourceList[preStep][1], 0, 'blue',
                                     self.sourceList[preStep][0])
                self.canvas.update()
                time.sleep(1)
            tkinter.messagebox.showinfo(title='提示', message='您好，当前算法已经演示完毕')
            self.state = 'end'
            for i in range(self.dataNumber):
                self.canvas.delete('lu' + str(i), 'pu' + str(i), 'tu' + str(i))
            self.canvas.update()
        else:
            tkinter.messagebox.showerror(title='警告', message='您好，请演示完毕后在执行该操作')

    # 加载图片,并缩放到条形图宽度
    def loadImage(self, filePath):
        imgDict = {}
        if os.path.exists(filePath):
            fileList = os.listdir(filePath)
            for preImgName in fileList:
                img = Image.open(filePath + preImgName)
                img = img.resize((40, 40), Image.ANTIALIAS)
                img = ImageTk.PhotoImage(img)
                imgDict[preImgName.split('.')[0]] = img
            return imgDict
        return None

    # 单步演示的时候绘制移动方向线
    def drawDirection(self, startIndex, endIndex):
        points = [startIndex * 70 + 40, 30, endIndex * 70 + 10, 30, endIndex * 70 + 35, 80, endIndex * 70 + 60, 40,
                  startIndex * 70 + 40, 40]
        self.canvas.create_polygon(points, outline='yellow', fill='red', width=3, tags='dire')

    # 绘制基本单位图像（包含条形图和文字描述#）,参数分别为，要绘制元素的位置，要绘制元素的值，元素是在上半部分还是在下半部分,或是整体（0 or 1,2）
    def drawBasicElemen(self, index, value, uOrD, color, imageName):
        # 绘制上半部分
        if uOrD == 0:
            self.canvas.create_line(index * 70 + 30, 300,
                                    index * 70 + 30,
                                    int(300 - 0.5 * self.preRectHeihPrc * value),
                                    width=self.preRectWidth, fill=color, tags="lu" + str(index))
            self.canvas.create_image(index * 70 + 30, 280 - 0.5 * self.preRectHeihPrc * value,
                                     image=self.imageDic[imageName], tags="pu" + str(index))
            self.canvas.create_text(index * 70 + 30,
                                    int(240 - 0.5 * self.preRectHeihPrc * value),
                                    text=str(value) + '亿$',
                                    tags="tu" + str(index))
        # 绘制下半部分
        elif uOrD == 1:
            self.canvas.create_line(index * 70 + 30, 600,
                                    index * 70 + 30,
                                    600 - 0.5 * self.preRectHeihPrc * value,
                                    width=self.preRectWidth, fill=color, tags="ld" + str(index))
            self.canvas.create_image(index * 70 + 30, 580 - 0.5 * self.preRectHeihPrc * value,
                                     image=self.imageDic[imageName], tags="pd" + str(index))
            self.canvas.create_text(index * 70 + 30,
                                    540 - 0.5 * self.preRectHeihPrc * value,
                                    text=str(value) + '亿$',
                                    tags="td" + str(index))
        # 整体绘制
        else:
            self.canvas.create_line(index * 70 + 30, 600,
                                    index * 70 + 30,
                                    600 - self.preRectHeihPrc * value,
                                    width=self.preRectWidth, fill=color, tags="la" + str(index))
            self.canvas.create_image(index * 70 + 30, 580 - self.preRectHeihPrc * value,
                                     image=self.imageDic[imageName], tags="pa" + str(index))
            self.canvas.create_text(index * 70 + 30,
                                    540 - self.preRectHeihPrc * value,
                                    text=str(value) + '亿$',
                                    tags="ta" + str(index))

    # 插入排序算法简介，一个应用程序只能有一个Tk入口,如果需要弹出多余的窗口，选择Toplevel代替
    def insertAlgorithmInfo(self):
        insertRoot = Toplevel()
        insertRoot.geometry('724x1025')
        img_open = Image.open('insertSortInfo.jpeg')
        img_open.thumbnail((724*0.9, 1025*0.9))
        img = ImageTk.PhotoImage(img_open)
        insertlabel = Label(insertRoot, image=img)
        insertlabel.pack()
        insertRoot.mainloop()

    # 插入排序中间步骤分解,列表中存储了每一步操作的中间结果，中间结果包括已经排序了的部分，以及被排序的元素移动到了已排序列表的那个位置
    def insertionSort(self):
        resault = []
        tempSourceList = copy.copy(self.sourceList)
        for i in range(self.dataNumber):
            if resault != []:
                temp = tempSourceList[i]
                isInsert = False
                for j in range(i, 0, -1):
                    if temp[1] < tempSourceList[j - 1][1]:
                        tempSourceList[j] = tempSourceList[j - 1]
                    else:
                        tempSourceList[j] = temp
                        resault.append([tempSourceList[:i + 1], j])
                        isInsert = True
                        break
                if isInsert == False:
                    tempSourceList[0] = temp
                    resault.append([tempSourceList[:i + 1], 0])
            else:
                resault.append([[self.sourceList[0]], 0])
        return resault


if __name__ == '__main__':
    a = Demonstrate()
